package com.zhupf.dynamic;

/**
 * @author zhupf
 * @date 2024年03月21日 15:14
 * @Description
 *
 *  279. 完全平方数
 */
public class NumSquares {

    public int numSquares(int n) {
        int[] f = new int[n+1];
        for(int i = 1 ; i<= n;i++){
            int minx = Integer.MAX_VALUE;
            for(int j = 1 ; j*j <= i;j++){
                minx = Math.min(f[i-j*j]+1,minx);
            }
            f[i] = minx;
        }
        return f[n];
    }
}
